Corelab Seminar
2014-2015
Vincent Chau (U. Evry - Val d'Essonne)
Throughput Maximization in the Speed-Scaling Setting
Abstract.
We are given a set of $n$ jobs and a single processor that can vary its speed dynamically.
Each job $J_j$ is characterized by its processing requirement (work) $p_j$, its release date $r_j$ and its deadline $d_j$.
We are also given a budget of energy $E$ and we study the scheduling problem of maximizing the throughput (i.e. the number
of jobs that are completed on time). While the preemptive energy minimization problem has been solved in polynomial time [Yao
et al., FOCS'95], the complexity of the problem of maximizing the throughput remained open until now. We answer partially this
question by providing a dynamic programming algorithm that solves the problem in pseudo-polynomial time. While our result shows
that the problem is not strongly NP-hard, the question of whether the problem can be solved in polynomial time remains a challenging
open question. Our algorithm can also be adapted for solving the weighted version of the problem where every job is associated
with a weight $w_j$ and the objective is the maximization of the sum of the weights of the jobs that are completed on time.